SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

In `F33f`_`[combinatorics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Combinatorics]`_`f and `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, `!covering problems`! are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are `F33f`_`[minimization problems`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Optimization_(mathematics)]`_`f and usually `F33f`_`[integer linear programs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Integer_linear_programs]`_`f, whose `F33f`_`[dual problems`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dual_problem]`_`f are called `F33f`_`[packing problems`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Packing_problems]`_`f.

The most prominent examples of covering problems are the `F33f`_`[set cover problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Set_cover_problem]`_`f, which is equivalent to the `F33f`_`[hitting set problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hitting_set]`_`f, and its special cases, the `F33f`_`[vertex cover problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Vertex_cover_problem]`_`f and the `F33f`_`[edge cover problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Edge_cover_problem]`_`f.

Covering problems allow the covering primitives to overlap; the process of covering something with non-overlapping primitives is called `F33f`_`[decomposition`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decomposition_(disambiguation)]`_`f.

>>Contents

• `F0af`_`[General linear programming formulation`#general-linear-programming-formulation]`_`f

• `F0af`_`[Kinds of covering problems`#kinds-of-covering-problems]`_`f

• `F0af`_`[Covering in Petri nets`#covering-in-petri-nets]`_`f

• `F0af`_`[Rainbow covering`#rainbow-covering]`_`f

• `F0af`_`[Conflict-free covering`#conflict-free-covering]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>General linear programming formulation

In the context of `F33f`_`[linear programming`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_programming]`_`f, one can think of any minimization linear program as a covering problem if the coefficients in the constraint `F33f`_`[matrix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Matrix_(mathematics)]`_`f, the objective function, and right-hand side are nonnegative.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] More precisely, consider the following general `F33f`_`[integer linear program`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Integer_linear_program]`_`f:

Such an integer linear program is called a `!covering problem`! if a j i , b j , c i ≥ ≥ 0 {\\displaystyle a_{ji},b_{j},c_{i}\\geq 0} for all i = 1 , … … , n {\\displaystyle i=1,\\dots ,n} and j = 1 , … … , m {\\displaystyle j=1,\\dots ,m} .

`!Intuition:`! Assume having n {\\displaystyle n} types of object and each object of type i {\\displaystyle i} has an associated cost of c i {\\displaystyle c_{i}} . The number x i {\\displaystyle x_{i}} indicates how many objects of type i {\\displaystyle i} we buy. If the constraints A x ≥ ≥ b {\\displaystyle A\\mathbf {x} \\geq \\mathbf {b} } are satisfied, it is said that `* x {\\displaystyle \\mathbf {x} } is a covering`* (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

>>Kinds of covering problems

There are various kinds of covering problems in `F33f`_`[graph theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_theory]`_`f, `F33f`_`[computational geometry`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_geometry]`_`f and more; see Category:Covering problems. Other stochastic related versions of the problem can be found.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>>Covering in Petri nets

For `F33f`_`[Petri nets`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Petri_net]`_`f, the covering problem is defined as the question if for a given marking, there exists a run of the net, such that some larger (or equal) marking can be reached. `*Larger`* means here that all components are at least as large as the ones of the given marking and at least one is properly larger.

>>>Rainbow covering

In some covering problems, the covering should satisfy some additional requirements. In particular, in the `!rainbow covering`! problem, each of the original objects has a "color", and it is required that the covering contains exactly one (or at most one) object of each color. Rainbow covering was studied e.g. for covering points by `F33f`_`[intervals`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Interval_(mathematics)]`_`f:`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]

• There is a set `*J`* of `*n`* colored intervals on the `F33f`_`[real line`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Real_line]`_`f, and a set `*P`* of points on the real line.

• A `F33f`_`[subset`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subset]`_`f `*Q`* of `*J`* is called a `*rainbow set`* if it contains at most a single interval of each color.

• A set of intervals `*J`* is called a `*covering`* of `*P`* if each point in `*P`* is contained in at least one interval of `*Q`*.

• The `*Rainbow covering problem`* is the problem of finding a rainbow set `*Q`* that is a covering of `*P`*.

The problem is `F33f`_`[NP-hard`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-hardness]`_`f (by reduction from `F33f`_`[linear SAT`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_SAT]`_`f).

>>>Conflict-free covering

A more general notion is `!conflict-free covering`!.`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f] In this problem:

• There is a set `*O`* of `*m`* objects, and a conflict-graph `*GO`* on `*O`*.

• A subset `*Q`* of `*O`* is called `*conflict-free`* if it is an `F33f`_`[independent set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Independent_set_(graph_theory)]`_`f in `*GO`*, that is, no two objects in `*Q`* are connected by an edge in `*GO`*.

• A rainbow set is a conflict-free set in the special case in which `*GO`* is made of disjoint cliques, where each clique represents a color.

`*Conflict-free set cover`* is the problem of finding a conflict-free subset of `*O`* that is a covering of `*P`*. Banik, Panolan, Raman, Sahlot and Saurabh`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f] `F33f`_`[prove`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematical_proof]`_`f the following for the special case in which the conflict-graph has bounded `F33f`_`[arboricity`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Arboricity]`_`f:

• If the geometric cover problem is `F33f`_`[fixed-parameter`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Fixed-parameter_algorithm]`_`f tractable (FPT), then the conflict-free geometric cover problem is FPT.

• If the geometric cover problem admits an r-approximation algorithm, then the conflict-free geometric cover problem admits a similar approximation algorithm in FPT time.

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefvazirani2001`a`F33f`_`[Vazirani, Vijay V.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Vijay_Vazirani]`_`f (2001). `*Approximation Algorithms`*. Springer-Verlag. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 3-540-65367-8.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefdouek-pinkovich-y-ben-gal-i-raviv-t-2022`aDouek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). "The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches" (PDF). European Journal of Operational Research, 299 (2022), 945–959}.`B100`F9d9{{cite web}}`f`b: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)

`:cite-note-3`!1.`! `:citerefajtai1973`a`F33f`_`[Ajtai, Miklós`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Miklós_Ajtai]`_`f (1973), "The solution of a problem of T. Radó", `*Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques`*, `!21`!: 61–63, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 0319053

`:cite-note-4`!2.`! `:citerefberegdumitrescujiang2010`aBereg, Sergey; Dumitrescu, Adrian; Jiang, Minghui (2010), "On covering problems of Rado", `*Algorithmica`*, `!57`! (3): 538–561, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s00453-009-9298-z, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 2609053; preliminary announcement in `F33f`_`[SWAT 2008`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SWAT_and_WADS_conferences]`_`f, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/978-3-540-69903-3_27

`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f `:citerefarkinbanikcarmicitovsky2018`aArkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "Selecting and covering colored points". `*Discrete Applied Mathematics`*. `!250`!: 75–86. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.dam.2018.05.011. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0166-218X.

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f `:citerefbaniksahlotsaurabh2020`aBanik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "Approximation algorithms for geometric conflict free covering problems". `*Computational Geometry`*. `!89`!: 101591. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.comgeo.2019.101591. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0925-7721. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 209959954.

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f `:citerefbanikpanolanramansahlot2020`aBanik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "Parameterized Complexity of Geometric Covering Problems Having Conflicts". `*Algorithmica`*. `!82`! (1): 1–19. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s00453-019-00600-w. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1432-0541. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 254027914.

`c`F0af`_`[↑ Back to top`#top]`_`f`a